package com.leetcode.linkedlist;

/**
 * 147. 对链表进行插入排序
 * 对链表进行插入排序。
 * 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
 * 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
 * 插入排序算法：
 * 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 * 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 重复直到所有输入数据插入完为止。
 * 示例 1：
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例2：
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/insertion-sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年11月18日 17:17
 */
 class Code147 {
    public static void main(String[] args) {
        Code147 code04 = new Code147();
        ListNode l0 = new ListNode(4);
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(3);
        l0.next = l1;
        l1.next = l2;
        l2.next = l3;
        System.out.println(l0);
        ListNode node =  code04.insertionSortList2(l0);
        System.out.println(node);
    }
    //4->2->1->3
    public ListNode insertionSortList1(ListNode head) {
        ListNode p = head;
        while (p != null){
            ListNode tar = findMin(p);
            if(tar != p){
                int temp = tar.val;
                tar.val = p.val;
                p.val = temp;
            }
            p = p.next;
        }
        return head;
    }
    public ListNode findMin(ListNode node) {
        ListNode p = node;
        ListNode minp = node;
        int min = node.val;
        while (p != null){
            if(p.val < min){
                min = p.val;
                minp = p;
            }
            p = p.next;
        }
        return minp;
    }

    /**
     * 官方题解
     * @author ymy
     * @date 2021/11/18 17:55
     * @param head
     * @return null
     */
    //4->2->1->3
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        //辅助接点，始终指向头结点，也相当于有序节点的头结点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        //指向有序节点的尾结点
        ListNode lastSorted = head;
        //待插入的节点
        ListNode curr = head.next;
        while (curr != null) {
            //有序节点尾结点小于待插入节点，直接追加
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                //否则从头节点遍历，寻找合适的插入点
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                //指针变换，将待插入节点插入合适位置
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
    /**
     * 复写官方题解
     * @author ymy
     * @date 2021/11/19 9:41
     * @param head
     * @return null
     */
    //4->2->1->3
    public ListNode insertionSortList2(ListNode head) {
        ListNode firstNode = head;
        ListNode lastNode = head.next;
        ListNode dumpHead = new ListNode(0);
        dumpHead.next = head;
        while(lastNode != null){
            if(firstNode.val < lastNode.val){
                firstNode = firstNode.next;
            }else{
                ListNode pre = dumpHead;
                while(pre.next.val <= lastNode.val){
                    pre = pre.next;
                }
                firstNode.next = lastNode.next;
                lastNode.next = pre.next;
                pre.next = lastNode;
            }
            System.out.println(dumpHead);
            lastNode = firstNode.next;
        }
        return  dumpHead.next;
    }


    static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
